#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/multi_array.hpp>

struct Item {
	int value;
	int weight;
};

//selection are initialized by 0s, return the total value of selected items
double fractional_knapsack(std::vector<Item> items, int weight, std::vector<double> & selection) {
	std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {return a.value*1.0/a.weight > b.value*1.0/b.weight;} );
	double value = 0;
	for (int i = 0; i < items.size(); ++i ) {
		if (items[i].weight < weight) {
			selection[i] =  items[i].weight;
			weight -= items[i].weight;
			value += items[i].value;
		}
		else {
			selection[i] = weight;
			value += items[i].value * 1.0 / items[i].weight * weight;
			break;
		}
	}
	return value;
}

////entries of c and r are initialized by -1 : indicate not calculated and no items selected respectively
//int binary_knapsack_r(int i, int j, int w, const std::vector<Item> &items, boost::multi_array<int,3> & c, boost::multi_array<int,3> & r){
//	if ( w <= 0 )
//		return 0;
//	if ( i > j )
//		return 0;
//	if ( c[i][j][w] >= 0 ) //memoized
//		return c[i][j][w];
//	if (i == j ){
//		if (items[i].weight <= w) {
//			c[i][j][w] = items[i].value;
//			r[i][j][w] = i;
//			return c[i][j][w];
//		}
//		else {
//			c[i][j][w] = 0;
//			return c[i][j][w];
//		}
//	}
//	for (int k = i; k <= j; ++k) {
//		if (items[k].weight <= w) {
//			int tmp = items[k].value + binary_knapsack_r(i, k-1, w-items[k].weight, items, c, r)
//				+ binary_knapsack_r(k+1, j, w-items[k].weight, items, c, r);
//			if (tmp  >= c[i][j][w]) {
//				c[i][j][w] = tmp;
//				r[i][j][w] = k;
//			}
//		}
//	}
//	return c[i][j][w];
//}
//
//void print_binary_knapsack_r(const std::vector<Item> &items,const boost::multi_array<int,3> & r, int i, int j, int w) {
//	if ( i > j || w <= 0 )
//		return;
//	int k = r[i][j][w];
//	std::cout << "item " << k << " is selected\n";
//	print_binary_knapsack_r(items,r,i,k-1,w-items[k].weight);
//	print_binary_knapsack_r(items,r,k+1,j,w-items[k].weight);
//}

int binary_knapsack_recursive(int i, int w, const std::vector<Item> & items, boost::multi_array<int,2> & c, std::vector<bool> & selection) {
	if ( w < 0 || i < 0 )
		return 0;
	if ( c[i][w] >= 0 ) //memoized
		return c[i][w];
	c[i][w]  = binary_knapsack_recursive(i-1, w, items, c, selection); //not select i
	selection[i] = false;
	if ( items[i].weight <= w ){
		int tmp = items[i].value + binary_knapsack_recursive(i-1, w-items[i].weight, items, c, selection);
		if ( tmp > c[i][w] ) {
			c[i][w] = tmp;
			selection[i] = true;
		}
	}
	return c[i][w];
}

int binary_knapsack_iterative(int n, int w, const std::vector<Item> & items, boost::multi_array<int,2> & c, std::vector<bool>& selection) {
	for (int j = 0; j <= w; ++j) 
		if (items[0].weight <= j)
			c[0][j] = items[0].value;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= w; ++j) {
			c[i][j] = c[i-1][j];
			selection[i] = false;
			if (items[i].weight <= j) {
				int tmp = items[i].value + c[i-1][j-items[i].weight];
				if (tmp > c[i][j]) {
					c[i][j] = tmp;
					selection[i] = true;
				}
			}
		}
	}
	return c[n-1][w];
}

void print_binary_knapsack(const std::vector<bool> & selection) {
	for (int i = 0; i < selection.size(); ++i) {
		if (selection[i])
			std::cout << "item " << i << " is selected\n";
	}
}

void test_knapsack() {
	int vi[] = {60, 100, 120};
	int wi[] = {10, 20, 30};
	int weight = 50;
	std::vector<Item> items(3);
	for (int i = 0; i < items.size(); ++i) {
		items[i].value = vi[i];
		items[i].weight = wi[i];
	}
	std::vector<double> selection(items.size());
	std::cout << "fractional knapsack: " << fractional_knapsack(items,weight,selection) << std::endl;
	for (int i = 0 ; i < selection.size(); ++i) {
		std::cout << "item " << i << " is selected " << selection[i] << " pounds\n";
	}
	/*boost::multi_array<int,3> c(boost::extents[items.size()][items.size()][weight+1]);
	boost::multi_array<int,3> r(boost::extents[items.size()][items.size()][weight+1]);
	const unsigned int * size = c.shape();

	for (int i = 0; i < size[0]; ++i)
		for (int j = 0; j < size[1]; ++j)
			for (int k = 0; k < size[2]; ++k){
				c[i][j][k] = -1;
				r[i][j][k] = -1;
			}
	std::cout << "binary knapsack: " << binary_knapsack_r(0,items.size()-1,weight,items,c,r) << std::endl;
	print_binary_knapsack_r(items,r,0, items.size()-1, weight);*/
	
	boost::multi_array<int,2> c(boost::extents[items.size()][weight+1]);
	const unsigned int * c_size = c.shape();
	for (int i = 0; i < c_size[0]; ++i)
		for (int j = 0; j < c_size[1]; ++j)
			c[i][j] = -1;
	std::vector<bool> selection1(items.size());
	std::cout << "binary knapsack(recursive): " << binary_knapsack_recursive(items.size()-1,weight,items,c,selection1) << std::endl;
	print_binary_knapsack(selection1);
	std::cout << "binary knapsack(iterative): " << binary_knapsack_iterative(items.size(),weight,items,c,selection1) << std::endl;
	print_binary_knapsack(selection1);

}